class Solution {
public:
    //Recursive method implementation
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if(left == 1 && right == 1) return head;
        if(left != 1){
            head->next = reverseBetween(head->next, left - 1, right - 1);
        }else{
            ListNode *tail = head->next;
            ListNode *new_head;
            new_head = reverseBetween(head->next, left, right - 1);
            head->next = tail->next;
            tail->next = head;
            head = new_head;
        }
        return head;
    }

    ListNode* reverseBetween2(ListNode* head, int left, int right) {
        ListNode new_head;
        new_head.next = head;
        ListNode *pre = &new_head;
        for (int i = 0; i < left - 1; i++) {
            pre = pre->next;
        }
        ListNode *cur = pre->next;
        ListNode *next;
        for (int i = 0; i < right - left; i++) {
            next = cur->next;
            cur->next = next->next;
            next->next = pre->next;
            pre->next = next;
        }
        return new_head.next;
    }
};